package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/ones-and-zeroes/
 */
public class P474 {

    //二维0-1背包问题,m和n均为背包的容量(m个0,n个1)
    //strs里的字符串就是商品
    //对每个子串(商品),有两个维度的重量,一个是0的重量，一个是1的重量
    //dp[i][j]表示装满i个0和j个1时，所需strs的最大子集的的长度
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(String str:strs){       //遍历物品
            int zero=0,one=0;       //记录0和1的数量
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)=='0'){
                    zero++;
                }else{
                    one++;
                }
            }
            //遍历两个维度的背包容量
            for(int i=m;i>=zero;i--){
                for(int j=n;j>=one;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);
                }
            }
        }
        return dp[m][n];
    }
}
